package leetcode10;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 51. N 皇后
 */
public class test58 {
    List<List<String>> list = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        char[][] str = new char[n][n];
        for(char[]c:str){
            Arrays.fill(c,'.');
        }
        back(str,0,n);
        return list;
    }
    public void back(char[][] str,int row,int n){
        if(row == n){
            list.add(ArrayList2(str));
            return;
        }
        for(int col = 0;col < n;col++){
            if(isPalid(row,col,n,str)){
                str[row][col] = 'Q';
                back(str,row + 1,n);
                str[row][col] = '.';
            }
        }
    }
    public boolean isPalid(int row,int col,int n,char[][] str){
        for(int i = 0;i < row;i++){
            if(str[i][col] == 'Q'){
                return false;
            }
        }
        for(int i = row - 1,j = col - 1;i >=0 && j >= 0;i--,j--){
            if(str[i][j] == 'Q'){
                return false;
            }
        }
        for(int i = row - 1,j = col + 1;i >= 0 && j <= n-1;i--,j++){
            if(str[i][j] == 'Q'){
                return false;
            }
        }
        return true;
    }
    public List<String> ArrayList2(char[][] str){
        List<String> a = new ArrayList<>();
        for (char[] c : str) {
            a.add(String.copyValueOf(c));
        }
        return a;
    }
}
